package pacman.entries.pacman;

import java.util.Arrays;
import java.util.EnumMap;

import pacman.game.Constants.GHOST;
import pacman.game.Constants.MOVE;

public class Node
{
	public final static int UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3; //for indexing the probabilities array
	public final static MOVE[] MOVES = new MOVE[] { MOVE.UP, MOVE.RIGHT, MOVE.DOWN, MOVE.LEFT }; //for convenience, corresponding to the above

	private double[] probabilities;
	private Node[][] matrix; //represents the child nodes as matrix[pacmanMoves][ghostMoves]
	private MOVE[] pacmanMoves; //the actual pacman moves, corresponding with the matrix
	private double score;
	private MyGame game; //for finding neighboring/child nodes
	private int pacmanLocation;
	private int[] identifyingPositions;
	int depth; //the depth that this node has already searched
	boolean search; //used for pruning

	public Node(MyGame game)
	{
		this.game = game;
		pacmanLocation = game.getPacmanLocation();
		identifyingPositions = game.getIdentifyingPositions();
		probabilities = new double[4];
		depth = -1;
		search = true;
	}

	/**
	 * Searches this root node, beginning at at a depth of initialDepth, and interrupting when the current time >= timeDue. If it manages to finish searching at a depth before time has run out, it will continue searching at a higher depth until time runs out. A root node will not check if it is a one where Pacman died or the level ended.
	 * 
	 * @param timeDue
	 *            The system time, in ms, of when this method should stop.
	 */
	public void evaluateRoot(long timeDue)
	{
		//after the first exploration of this Node, the neighbors are already there and shouldn't be recalculated
		if (matrix == null)
		{
			depth = 0;
			calculateNeighbors();
		}

		//have to constantly check if time is up, here as well as evaluate(int, long)
		while (System.currentTimeMillis() < timeDue && depth < 1000)
		{
			for (Node[] row : matrix)
			{
				for (Node cell : row)
				{
					//if we run out of time, or if one of the child nodes we're evaluating already interrupted, interrupt this as well
					if (System.currentTimeMillis() >= timeDue)
					{
						return;
					}
					cell.evaluate(depth, timeDue);
					//if the child node didn't search up to the requested depth AND it wasn't pruned, we know it interrupted
					if (cell.search && cell.depth < depth)
					{
						return;
					}
				}
			}
			if (System.currentTimeMillis() >= timeDue)
				return;
			score = nash(); //minimax			
			depth++; //only search deeper when this current depth has fully been searched (and wasn't interrupted earlier)
		}

		return;
	}

	/**
	 * Searches this nonroot node to a depth of depth, and interrupting when the current time >= timeDue. A nonroot node will check if it is one where Pacman died or the level ended, in which case it will stop searching beyond that.
	 * 
	 * @param depth
	 *            The depth to search this node.
	 * @param timeDue
	 *            The system time, in ms, of when this method should stop.
	 */
	public void evaluate(int targetDepth, long timeDue)
	{
		//also see documentation in evaluateRoot
		if (depth >= targetDepth || !search)
			return;

		if (matrix == null)
		{
			depth = 0;

			//note that when recalculating this node to a depth greater than 0, matrix will still be null because it is never initialized with depth 0
			if (targetDepth == 0 || game.isReset()) //stop searching when Pacman dies or level ends
			{
				score = game.evaluate(); //heuristic
				if (game.isReset())
					search = false; //prune
				return;
			}

			if (System.currentTimeMillis() >= timeDue)
				return;
			calculateNeighbors();
		}

		boolean keepSearching = false;
		for (Node[] row : matrix)
			for (Node cell : row)
			{
				if (System.currentTimeMillis() >= timeDue)
					return;
				cell.evaluate(targetDepth - 1, timeDue);
				if (cell.search)
				{
					keepSearching = true; //there exists at least one child node that isn't pruned
					if (cell.depth < targetDepth - 1)
						return;
				}
			}

		if (System.currentTimeMillis() >= timeDue)
			return;
		score = nash();
		depth = targetDepth;
		if (!keepSearching) //if there is no child node that isn't pruned
			search = false; //prune this node as well
		return;
	}

	public Node getChild(int[] identifyingPositions)
	{
		//find child node based on identifyingPositions
		for (Node[] row : matrix)
			for (Node cell : row)
				if (Arrays.equals(cell.getIdentifyingPositions(), identifyingPositions))
				{
					return cell;
				}
		return null;
	}

	private void calculateNeighbors()
	{
		pacmanMoves = game.getPacmanMoves(); //possible moves Pacman can make
		EnumMap<GHOST, MOVE>[] ghostMoves = game.getGhostMoves(); //possible sets of moves ghosts can make
		int nPacman = pacmanMoves.length, nGhost = ghostMoves.length;
		matrix = new Node[nPacman][nGhost];
		for (int i = 0; i < nPacman; i++)
			for (int j = 0; j < nGhost; j++)
			{
				//get the neighboring gamestate based on pacman moving a certain direction and the ghosts moving certain directions
				//"neighboring" as in as far as pacman and the ghosts can go before the game branches (has multiple following gamestates), e.g. when a ghost reaches a junction
				//see Game documentation for more details
				MyGame neighbor = game.getNeighbor(pacmanMoves[i],
						new EnumMap<GHOST, MOVE>(ghostMoves[j])); //we must create a new copy because the implementation of Game modifies ghostMoves, which will mess this up when calculating other neighbors
				//and create the neighboring node from the neighboring gamestate
				matrix[i][j] = new Node(neighbor);
			}
		game = null; //no longer need
	}

	public double getScore()
	{
		return score;
	}

	/**
	 * Gets the child node based on identifyingPositions. Child nodes may be more than one tick away from the current node since, so they are identified by identifyingPositions, which represents the positions of Pacman and the ghosts 1 tick away from the current node (along the way to the actual child node).
	 * 
	 * @param identifyingPositions
	 *            The positions of Pacman and the ghosts one tick away from the current node, along the way to the child node.
	 * @return The child node.
	 */
	public double[] getProbabilities()
	{
		return probabilities;
	}

	public int getPacmanLocation()
	{
		return pacmanLocation;
	}

	public int[] getIdentifyingPositions()
	{
		return identifyingPositions;
	}

	private double nash()
	{
		int nPacman = matrix.length, nGhosts = matrix[0].length;
		for (int i = 0; i < 4; i++)
			probabilities[i] = 0; //reset
		//two special cases
		//if pacman has one move, that move has probability 100%, and the score is the lowest possible one
		if (nPacman == 1)
		{
			double min = Double.POSITIVE_INFINITY;
			for (int c = 0; c < nGhosts; c++)
			{
				if (matrix[0][c].getScore() < min)
					min = matrix[0][c].getScore();
			}
			switch (pacmanMoves[0])
			{
			case UP:
				probabilities[UP] = 1;
				break;
			case RIGHT:
				probabilities[RIGHT] = 1;
				break;
			case DOWN:
				probabilities[DOWN] = 1;
				break;
			case LEFT:
				probabilities[LEFT] = 1;
				break;
			}
			return min;
		}
		//if ghosts only have one move, then all of pacman's moves that yield the highest score have equal probability
		if (nGhosts == 1)
		{
			double max = Double.NEGATIVE_INFINITY;
			int nMax = 0;
			for (int r = 0; r < nPacman; r++)
			{
				double score = matrix[r][0].getScore();
				if (score > max)
				{
					max = score;
					nMax = 1;
				} else if (score == max)
				{
					nMax++;
				}
			}
			for (int r = 0; r < nPacman; r++)
			{
				if (matrix[r][0].getScore() == max)
				{
					switch (pacmanMoves[r])
					{
					case UP:
						probabilities[UP] = 1d / nMax;
						break;
					case RIGHT:
						probabilities[RIGHT] = 1d / nMax;
						break;
					case DOWN:
						probabilities[DOWN] = 1d / nMax;
						break;
					case LEFT:
						probabilities[LEFT] = 1d / nMax;
						break;
					}
				}
			}
			return max;
		}
		//otherwise, linear programming is used to find the nash equilibrium mixed strategy (probabilities) and score
		//I won't bother documenting this beyond what I wrote already, it should be reliable and you can just trust it to work -_-
		int width = nPacman + nGhosts + 3; //+nGhosts for slack variables, +2 for additional unbounded variable r, +1 for right hand side
		double[][] constraints = new double[nGhosts + 1][width];
		//-a_0,c - a_1,c - ... - a_(nPacman-1),c + r1 - r2 + slack = 0
		for (int r = 0; r < nGhosts; r++)
		{
			for (int c = 0; c < nPacman; c++)
			{
				constraints[r][c] = -matrix[c][r].getScore();
			}
			//expressing r as r1 - r2 (r1,r2 >= 0) since r is unbounded
			constraints[r][nPacman] = 1;
			constraints[r][nPacman + 1] = -1;
			//slack variable
			constraints[r][nPacman + 2 + r] = 1;
		}
		for (int c = 0; c < nPacman; c++)
			constraints[nGhosts][c] = 1;
		constraints[nGhosts][width - 1] = 1;
		double[] objective = new double[nPacman + 2];
		//minimizing -r aka -(r1 - r2) = -r1 + r2
		objective[nPacman] = -1;
		objective[nPacman + 1] = 1;

		double[] strategy = LP.calculate(objective, constraints);
		for (int i = 0; i < nPacman; i++)
		{
			double probability = strategy[i];
			switch (pacmanMoves[i])
			{
			case UP:
				probabilities[UP] = probability;
				break;
			case RIGHT:
				probabilities[RIGHT] = probability;
				break;
			case DOWN:
				probabilities[DOWN] = probability;
				break;
			case LEFT:
				probabilities[LEFT] = probability;
				break;
			}
		}
		return strategy[nPacman] - strategy[nPacman + 1];
	}

	@Override
	public String toString()
	{
		String string = "";
		for (int i = 0; i < matrix.length; i++)
		{
			Node[] row = matrix[i];
			for (Node column : row)
			{
				string += column.getScore() + (column.search ? "\t" : "p\t");
			}
			string += pacmanMoves[i] + "\n";
		}
		return string;
	}

}